1. Field of the Invention
The present invention relates generally to the field of network communications, and more particularly to an apparatus and method for traffic shaping in a network switch.
2. Description of the Related Art
In general, network communication systems interconnect many users in a network. Each user is connected to the network through a port. The network is formed by the interconnection of many nodes, whereby information input at an input port from one user at a source is passed from node to node through the network to an output port and to another user at a destination. The information transferred from source to destination is packetized and each node switches incoming packets at incoming ports to outgoing packets at outgoing ports. For ATM (Asynchronous Transfer Mode) networks, the packets are further divided into cells.
Using current technology, fast packet switches transfer hundreds of thousands of packets per second at every switch port. Each switch port is typically designed to transfer information at a rate from 50 Mbit/s to 2.4 Gbit/s for a broadband integrated service digital network (BISDN). Switch sizes range from a few ports to thousands of ports.
The term xe2x80x9cfast packet switchxe2x80x9d includes switches capable of handling both variable length packets and fixed length packets. Use of fixed-length packets can simplify the switch design. Fast packet switches using short, fixed-length packets (cells) are referred to as ATM switches. Fast packet switches handle different types of communications services in a single integrated network where such services may include voice, video and data communications. Since voice and video services can tolerate only a limited amount of delay and delay variance through a network, ATM switches are suitable for such services. The ATM standard for broadband ISDN networks defines a cell having a length of 53 bytes with a header of 5 bytes and data of 48 bytes. The ATM Forum Traffic Management Specification has specified a number of Service Class Definitions as follows:
CBR: Continuous Bit Rate. For real-time applications requiring tightly constrained delay and delay variation such as voice and video. The CBR service class requires the consistent availability of a fixed quantity of bandwidth.
RT-VBR: Realtime Variable Bit Rate. For applications where sources transmit at a rate which varies with time (referred to in the art as xe2x80x9cburstyxe2x80x9d), yet still must receive service with tightly constrained delay and delay variation.
NRT-VBR: Non-Realtime Variable Bit Rate. For bursty applications, having no service requirements related to delay or its variance, but having sensitivity to loss.
UBR: Unspecified Bit Rate. For non-real-time applications, such as file transfer and e-mail, that transmit non-continuous bursts of cells without related service guarantees and therefore without allocated bandwidth resource, without guarantee as to cell loss ratio or cell transfer delay, and without explicit feedback regarding current level of network congestion.
GFR: Guaranteed Frame Rate. Also for non-real-time applications, this service category provides loss guarantees for sources transmitting traffic at or below a contracted minimum rate. Once a source exceeds the contracted minimum rate, traffic above that rate does not receive any loss guarantees.
ABR: Available Bit Rate. For non-real-time applications that permit variation in information transfer rate depending on the amount of bandwidth available in the network.
In a typical ATM switch, the cell processing functions are performed within the nodes of a network. Each node is an ATM switch which includes input controllers (IC""s), a switch fabric (SF), output controllers (OC""s) and a node control (C). The node control is used for functions including connection establishment and release, bandwidth reservation, buffering control, congestion control, maintenance and network management.
In each switch, the input controllers are typically synchronized so that all cells from input controllers arrive at the switch fabric at the same time and cells can be accepted or rejected according to their priority. The traffic through the switch fabric is slotted and the switch fabric delay equals the sum of the timeslot duration, pipeline delay and the queuing delay.
The node control communicates with the input controllers and the output controllers either by a direct communication path which by-passes the switch fabric or via control cells transmitted through the switch fabric.
External connections to the switch are generally bi-directional. Bi-directional connections are formed by grouping an input controller (IC) and an output controller (OC) together to form a port controller (PC).
The input sequence of cells in a virtual channel is preserved across the switch fabric so that the output sequence of cells on each virtual channel is the same as the input sequence. Cells contain a virtual channel identifier (VCI) in the cell header which identifies the connection to which the cell belongs. Each incoming VCI in the header of each cell is translated in an input controller to specify the outgoing VCI identifier. This translation is performed in the input controller typically by table look-up using the incoming VCI to address a connection table. This connection table also contains a routing field to specify the output port of the switch fabric to which the connection is routed. Other information may be included in the connection table on a per connection basis such as the priority, class of service, and traffic type of the connection.
In an ATM switch, cell arrivals are not scheduled. In a typical operation, a number of cells may arrive simultaneously at different input ports, each requesting the same output port. Operations in which requests exceed the output capacity of the output port are referred to as output contention. Since an output port can only transmit a fixed number (for example, one) cell at a time, only the fixed number of cells can be accepted for transmission so that any other cells routed to that port must either be discarded or must be buffered in a queue. Different methods are employed for routing cells through a switch module, for example, self-routing and label routing.
A self-routing network operates with an input controller prefixing a routing tag to every cell. Typically, the input controller uses a table look-up from a routing table to obtain the routing tag. The routing tag specifies the output port to which the cell is to be delivered. Each switching element is able to make a fast routing decision by inspecting the routing tag. The self-routing network ensures that each cell will arrive at the required destination regardless of the switch port at which it enters.
A label routing network operates with a label in each cell referencing translation tables in each switching element. The label is translated in each switching element and hence any arbitrary network of switching elements may be employed.
Switches have two principal designs, time-division and space division. In a time-division switch fabric, all cells flow through a single communication channel shared in common by all input and output ports. In a space division switch, a plurality of paths are provided between the input and output ports. These paths operate concurrently so that many cells may be transmitted across the switch fabric at the same time. The total capacity of the switch fabric is thus the product of the bandwidth of each path and the average number of paths that can transmit a cell concurrently.
When the traffic load exceeds the available system resources in a network, congestion is present and performance degrades. When the number of cells is within the carrying capacity of the network, all cells can be delivered so that the number of cells delivered equals the number of cells sent without congestion. However, if cell traffic is increased to the level that nodes cannot handle the traffic, congestion results.
Congestion can be brought about by several factors. If nodes in a network are too slow to perform the various tasks required of them (queuing buffers, updating tables, etc.), queues build up, even though excess line capacity exists. On the other hand, even if nodes are infinitely fast, queues will build up whenever the input traffic rate exceeds the capacity of the output traffic rate for any particular group of outputs.
If a node has no free buffers for queuing cells, the node must discard newly arriving cells. For packet data traffic, when a cell is discarded, the packet from which the discarded cell came will be retransmitted, perhaps many times, further extending the congestion epoch.
In an ATM switch, in order to guarantee a certain service rate, the flow of incoming data needs to be predictable, thereby allowing a designer to provide adequate buffer space. One problem which arises is that the cells do not arrive with a uniform distribution. In fact, most traffic arrives in xe2x80x9cburstsxe2x80x9dxe2x80x94with a cell group, having a random size, transmitted in between delays of random duration. In order to provide for a more predictable data stream, the cell bursts are shaped by a device known in the art as a xe2x80x9cshaper.xe2x80x9d The shaper takes the cell bursts and distributes the cells evenly, according to a predefined xe2x80x9cshape.xe2x80x9d Different virtual channels (VCs) may require different shapes, and therefore it would be desirable to have a shaper that shapes each VC independently.
In general, the present invention is an apparatus and method for traffic shaping in a network switch, which provides for per-connection shaping. A shaper according to the present invention comprises two functional blocks: a Cell Descriptor (CD) processing block, and a ShapeID processing block. The CD processing block and the ShapeID processing block operate to de-couple the management of the CDs from the scheduling of the CD output times. The CD-processing block outputs a token (ShapeID) to the ShapeID block. If the token is conforming, it is immediately passed back to the CD-processing block, otherwise it is processed. When the token is xe2x80x9cmaturexe2x80x9d the token is passed back to the CD-processing block. The CD processing block then outputs a CD.
Use of xe2x80x9cnowxe2x80x9d and xe2x80x9claterxe2x80x9d lists with per-connection ShapeIDs provides priority within a virtual connection (VC) and a virtual path (VP), respectively. This effectively preserves the relative priority for connections being shaped within a VP. In other words, a higher priority VC may be sent first, even if it did not generate the token, thus preserving cell priority. Also, the use of a Calendar Queue reduces the complexity of a xe2x80x9cvirtual finishing timexe2x80x9d (VFT) calculation.